from typing import *
from bisect import bisect_left, bisect_right


class Solution:

    def maxNumberOfAlloys(self, n: int, k: int, budget: int,
                          composition: List[List[int]], stock: List[int],
                          cost: List[int]) -> int:
        l, r = 0, 10**9
        while l < r:
            m = ((r - l) >> 1) + l
            f = False
            for comp in composition:
                tot = 0
                for i, c in enumerate(comp):
                    n = max(c * m - stock[i], 0)
                    tot += n * cost[i]
                if tot <= budget:
                    f = True
                    break
            if f:
                l = m + 1
            else:
                r = m

        return l - 1


s = Solution()
print(
    s.maxNumberOfAlloys(n=3,
                        k=2,
                        budget=15,
                        composition=[[1, 1, 1], [1, 1, 10]],
                        stock=[0, 0, 0],
                        cost=[1, 2, 3]))


class Solution:

    def maxNumberOfAlloys(self, n: int, k: int, budget: int,
                          composition: List[List[int]], stock: List[int],
                          cost: List[int]) -> int:
        return max(
            bisect_left(range(1000000000),
                        True,
                        key=lambda x: sum(
                            max(0, x * m - s) * c
                            for m, s, c in zip(mc, stock, cost)) > budget)
            for mc in composition) - 1


class Solution:

    def maxNumberOfAlloys(self, n: int, k: int, budget: int,
                          composition: List[List[int]], stock: List[int],
                          cost: List[int]) -> int:
        return max(
            bisect_right(range(1000000000),
                         budget,
                         key=lambda x: sum(
                             max(0, x * m - s) * c
                             for m, s, c in zip(mc, stock, cost)))
            for mc in composition) - 1
